package org.basic.algorithm.medium.offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
 * candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
 * <p>
 * 示例 1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8
 * 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
 * <p>
 * 示例 2:
 * 输入: candidates = [2,5,2,1,2], target = 5
 * 输出: [ [1,2,2], [5] ]
 *
 * @author LiKun
 * @date 2021/10/28 16:13
 */
public class RepeatingElementCollection {
    public static List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        System.out.println(combinationSum2(new int[]{4, 2, 5, 2, 5, 3, 1, 5, 2, 2}, 9));
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);                                       // 先对数组进行排序，以便后续处理

        RepeatingElementCollection.recursion(candidates, target, 0, new ArrayList<>(0), false);

        // 筛选掉 result 中的重复项数据集；注：此处及其影响效率
        for (int i = 0; i < result.size(); i++) {
            List<Integer> preElement = result.get(i);
            for (int j = i + 1; j < result.size(); j++) {
                if (preElement.size() == result.get(j).size() && preElement.equals(result.get(j))) {
                    result.remove(j--);
                }
            }
        }
        return result;
    }

    /**
     * 递归处理数组，并将结果放入到 result 集合中
     *
     * @param candidates   源数组
     * @param target       给定的值
     * @param index        本次便利起始索引
     * @param parContainer 本次便利存放结果集
     */
    private static void recursion(int[] candidates, int target, int index, List<Integer> parContainer, boolean allowDuplicates) {
        // 使用 index 的好处：减少遍历次数；不需要对最终结果进行去重(例：不会出现 [[3, 5, 5], [5, 3, 5], [5, 5, 3]] 的情况)；
        for (; index < candidates.length && candidates[index] <= target; index++) {
            if (allowDuplicates || (index == 0 || candidates[index - 1] != candidates[index])) {
                if (candidates[index] << 1 <= target) {                        // candidates[index] <= target - candidates[index] ---> 还存在可能被选取的值
                    List<Integer> container = new ArrayList<>(parContainer);
                    container.add(candidates[index]);

                    // 递归寻找剩余的匹配项
                    recursion(candidates, target - candidates[index], index + 1, container, true);
                } else if (candidates[index] == target) {                      // 本轮递归结束条件 ---> 最后一个被选取的值
                    parContainer.add(candidates[index]);
                    result.add(parContainer);
                    break;
                }
            }
        }
    }
}
